#include <stdio.h>
#include <stdlib.h>
#include<algorithm>
#include <string.h>
#include <iostream>
#include <unistd.h>
#include <ctime>
#include <climits>
#define MAX 512   // 内存总大小为512K
using namespace std;
const int pLength = 8;      // 最大分区数
 
struct Partition{
    char pName[20];     // 内存分区名字
    int start;          // 起始地址
    int size;           // 地址空间大小
    bool status;        // 内存分区状态,true为空表
};
Partition partitions[pLength];          // 内存分区最多8个
Partition partitions_All[pLength];
 
const int aLength = 5;
struct Assignment{
    int uid;            // 作业编号
    char aName[20];     // 作业名字
    int asize;          // 作业大小
    int startAddress;   // 作业起始地址
    int arriveTime;     // 到达时间
    int startTime;      // 开始工作时间
    int runTime;        // 工作时间
    Assignment *next;   // 链表连接
};
Assignment assignments[aLength];    // 作业
Assignment* waitA;                  // 等待工作
 
int endCount;
int clockTime;
int sequence[aLength];
int flag;               // 全局变量记录回收类型
 
// 判断大小
bool cmp(Partition a, Partition b) {
    return a.size < b.size;
}
 
// 单分区情况
void outPut(int i){
    printf("%s\t\t%d\t\t\t%d\t\t%d\n", partitions[i].pName, partitions[i].start, partitions[i].size, partitions[i].status);
}
 
void printInfo(){
    printf("Name\t\tStart_Address\t\tSize\t\tStatus\n");
    for(int i = 0; i < pLength; i++){
        printf("%s\t\t%d\t\t\t%d\t\t%d\n", partitions_All[i].pName, partitions_All[i].start, partitions_All[i].size, partitions_All[i].status);
    }
}
 
void init(){
    strcpy(partitions_All[0].pName, "OS");
    partitions_All[0].start = 0;     // 起始地址0，长度10
    partitions_All[0].size = 10;
    partitions_All[0].status = false;
 
    strcpy(partitions_All[1].pName, "TEST1");
    partitions_All[1].start = 10;   // 起始地址10，长度10
    partitions_All[1].size = 10;
    partitions_All[1].status = false;
 
    strcpy(partitions_All[2].pName, "TEST4");
    partitions_All[2].start = 20;   // 起始地址20，长度25
    partitions_All[2].size = 25;
    partitions_All[2].status = false;
 
    strcpy(partitions_All[3].pName, "---");
    partitions_All[3].start = 45;   // 起始地址45，长度20
    partitions_All[3].size = 20;
    partitions_All[3].status = true;
 
    strcpy(partitions_All[4].pName, "TEST2");
    partitions_All[4].start = 65;   // 起始地址65，长度45
    partitions_All[4].size = 45;
    partitions_All[4].status = false;
 
    strcpy(partitions_All[5].pName, "---");
    partitions_All[5].start = 110;   // 起始地址110，长度40
    partitions_All[5].size = 40;
    partitions_All[5].status = true;
 
    strcpy(partitions_All[6].pName, "---");
    partitions_All[6].start = 150;   // 起始地址150，长度40
    partitions_All[6].size = 40;
    partitions_All[6].status = true;
 
    strcpy(partitions_All[7].pName, "---");
    partitions_All[7].start = 190;   // 起始地址180，长度45
    partitions_All[7].size = 45;
    partitions_All[7].status = true;
 
    int count = 0;     // 提取空闲区
    for(int i = 0; i < pLength; i++){
        if(partitions_All[i].status == true) {
            partitions[count] = partitions_All[i];
            count++;
        }
    }
    for(int i = count; i < pLength; i++){
        partitions[i].status = false;
        partitions[i].size = INT_MAX;
    }
    printf("==========================================================\n");
    printf("|                 欢迎使用最佳适应算法测试系统                 |\n");
    printf("|             状态1为盈余空间，状态0为已被占用！                |\n");
    printf("|                                                        |\n");
    printf("==========================================================\n\n");
    printf("初始化内存使用情况：\n");
    printInfo();
    printf("\n初始化作业队列：\n");
    printf("Uid\t\tAssignment_Size\t\tArriveTime\tRunTime\n");
    srand(GetTickCount());
    for(int i = 0; i < 5; i++){
        assignments[i].uid = i + 1;
        assignments[i].asize = ((float) rand()/32767) * 40 + 10;
        assignments[i].arriveTime = ((float) rand()/32767) * 20;
        assignments[i].runTime = ((float) rand()/32767) * 20;
        assignments[i].startTime = -INT_MAX;
        printf("%d\t\t%d\t\t\t%d\t\t%d\n", assignments[i].uid, assignments[i].asize, assignments[i].arriveTime, assignments[i].runTime);
    }
}
 
// 展示内存空闲分区情况
void display() {
    printf("\tStart_Address\t\tSize\t\tStatus\n");
    for(int i = 0; i < pLength; i++){
        // 占用
        if(partitions[i].status == false) {
            printf("\t---\t\t\t---\t\t0\n");
        } else{
            printf("\t%d\t\t\t%d\t\t%d\n", partitions[i].start, partitions[i].size, partitions[i].status);
        }
    }
}
// 分配内存
bool distribute(int pos){
    // 申请主存
    for(int i = 0; i < pLength; i++) {
        // 未分配吗？
        if(partitions[i].status == false)
            return false;
        // 长度大于等于作业
        if(partitions[i].size >= assignments[pos].asize) {
            printf("分配空间成功！\n");
            printf("作业序号：%d\n", assignments[pos].uid);
            printf("作业大小：%d\n", assignments[pos].asize);
            printf("到达时间：%d\n", assignments[pos].arriveTime);
            printf("工作时间：%d\n", assignments[pos].runTime);
 
            assignments[pos].startTime = clockTime;                 // 启动时间为时钟时间
            assignments[pos].startAddress = partitions[i].start;    // 分配内存起始地址
 
            // 置状态为空表目
            if(partitions[i].size == assignments[pos].asize) {
                partitions[i].status = false;    // 不空
                partitions[i].size = INT_MAX;
                strcpy(partitions[i].pName, "***");
            } else {
                // 长度-= 地址+=
                partitions[i].start += assignments[pos].asize;
                partitions[i].size -= assignments[pos].asize;
            }
            // 将长度已经减少的表目向前排序，使空闲区表按大小排序
            sort(partitions, partitions + pLength, cmp);
            printf("分配后的空闲分区使用情况：\n");
            display();
            //printInfo();
            return true;
        }
    }
    return false;
}
 
// 释放内存
void remove(int pos) {
    flag = 0;
    for(int i = 0; i < pLength; i++){
        if(partitions[i].status == false) {
            partitions[i].start = assignments[pos].startAddress;
            partitions[i].size = assignments[pos].asize;
            partitions[i].status = true;    // 未使用状态
            flag = 1;       // 上下均无邻接
            break;
        }
        if(i < 99 && partitions[i].start + partitions[i].size == assignments[pos].startAddress &&
           partitions[i+1].start == assignments[pos].startAddress + assignments[pos].asize) { // 上下衔接情况
            partitions[i].size += partitions[i+1].size + assignments[pos].asize;   // 合并情况
            partitions[i+1].status = false;   // 未使用状态
            partitions[i+1].size = INT_MAX;    // 置空
            flag = 2;      // 与上下空闲区邻接情况
            break;
        } else if(partitions[i].start + partitions[i].size == assignments[pos].startAddress) { // 上衔接情况
            partitions[i].size += assignments[pos].asize;
            flag = 3;     // 与上空闲区邻接情况
            break;
        } else if(partitions[i].start == assignments[pos].startAddress + assignments[pos].asize) {
            partitions[i].start = assignments[pos].startAddress;     // 下衔接情况
            partitions[i].size += assignments[pos].asize;
            flag = 4;     // 与下空闲区邻接情况
            break;
        }
    }
    printf("回收空间成功！");
    printf("作业序号：%d\n", assignments[pos].uid);
    printf("作业大小：%d\n", assignments[pos].asize);
    printf("到达时间：%d\n", assignments[pos].arriveTime);
    printf("工作时间：%d\n", assignments[pos].runTime);
    switch (flag) {
        case 0:
            printf("ERROR!\n");
            break;
        case 1:
            printf("\t释放区与空闲区不邻接！\n");
            break;
        case 2:
            printf("\t释放区上下都与空闲区邻接！\n");
            break;
        case 3:
            printf("\t释放区与上空闲区邻接！\n");
            break;
        case 4:
            printf("\t释放区与下空闲区邻接！\n");
            break;
    }
    // 将长度已经减少的表目向前排序，使空闲区表按大小排序
    sort(partitions, partitions + pLength, cmp);
    printf("回收后的空闲分区使用情况：\n");
    display();
    //printInfo();
    endCount++; // 结束
}
 
// 工作区
void Test(){
    clockTime = 0; // 时间为0
    endCount = 0; // 没有结束工作
    waitA = NULL;
    int index = 0; // 定义作业释放顺序下标
    while(endCount < aLength){ // 作业未完成循环检测
        printf("====================================================\n");
        printf("时钟：%d\n", clockTime);
        printf("空闲区说明表：\n");
        display();
        //printInfo();
        for(int i = 0; i < aLength; i++){
            if(assignments[i].arriveTime == clockTime){ // 作业是否到达？
                if(waitA == NULL){ // 当前没有等待
                    assignments[i].next = NULL; // 队列链接 ——直接放入
                    waitA = &assignments[i];
                } else { // 当前有等待的队列作业
                    Assignment *p = waitA; // 队列迁移
                    while(p->next != NULL){ // 寻找队尾
                        p=p->next;
                    }
                    assignments[i].next = NULL;
                    p->next = &assignments[i];
                }
            }
        }
        // 存在等待队列的情况
        if(waitA != NULL) {
            Assignment *p = waitA;
            // 检测是否有允许分配的
            while(p->next != NULL) {
                if (distribute(p->next->uid-1) == true) { // 允许分配
                    p->next = p->next->next;
                } else {
                    p = p->next;
                }
            }
            if (distribute(waitA->uid-1) == true) { // 当前可以工作
                waitA = NULL;
            }
        }
        for(int i = 0; i < aLength; i++) {
            if(assignments[i].startTime + assignments[i].runTime == clockTime) {
                remove(i); // 释放作业
                sequence[index] = assignments[i].uid;
                index++;
            }
        }
        clockTime++;
    }
}
 
void printSequence() {
    printf("\n系统作业释放顺序为：");
    for(int i = 0; i < aLength; i++){
        if(i != aLength - 1){
            printf("%d->", sequence[i]);
        } else{
            printf("%d\n", sequence[i]);
        }
    }
}
 
int main() {
    init();
    Test();
    printSequence();
}